import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

// 串联所有单词的子串
//测试链接 https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/

public class FindSubstring {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>(); //存放答案

        HashMap<String,Integer> tagert = new HashMap<>();
        for(String temp : words){
            tagert.put(temp, tagert.getOrDefault(temp,0) + 1);
        }

        int n = s.length();//字符串的长度
        int  len = words[0].length(), m = words.length;   //数组单个字符串的长度； 整个有效字符串的个数

        for(int i = 0; i < len; i ++){ //len次滑动窗口

            HashMap<String, Integer> cur = new HashMap<>();
            int cnt = 0; //记录有效字符
            for(int left = i, right = i; right + len <= n; right += len){

                String in = s.substring(right, right+len) ; //截取字符串
                cur.put(in, cur.getOrDefault(in,0) + 1); //进窗口
                if(cur.get(in) <= tagert.getOrDefault(in,0)){ //判断有效的字符个数
                    cnt++;
                }

                while(right - left + 1 > m * len){ //出窗口
                    String out = s.substring(left,left+len);
                    cur.put(out, cur.get(out) - 1);

                    if(cur.get(out) < tagert.getOrDefault(out,0)){ //判断有效的字符个数
                        cnt--;
                    }

                    left += len;
                }
                //判断
                if(cnt == m){
                    ans.add(left);
                }
            }
        }

        return ans;
    }
}
